package com.example.system.class24;

/**
 * @Date 2022/8/24
 * @Author Jonathan
 * @Description 给定一个正数数组arr，
 * 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
 * 返回：
 * 最接近的情况下，较小集合的累加和
 */
public class Code01_SplitSumClosed {
    public static void main(String[] args) {// 1:47
        System.out.println(splitSumClosed(new int[]{1, 2, 3, 100, 10}));
    }


    public static int splitSumClosed(int[] arr) {
        return process(arr, 0, getSum(arr) >> 1);
    }


    public static int process(int[] arr, int index, int rest) {
        // 怎么扣这个边界？
        // 走到这里说明已经没有数据 返回0即可
        if (index == arr.length) {
            return 0;
        }

        int p1 = process(arr, index + 1, rest); // index位置不要
        int p2 = -1;
        // 当前这个值要不超过rest的时候用进去
        if (arr[index] <= rest) {
            p2 = process(arr, index + 1, rest - arr[index]) + arr[index];
        }
        // pass
        return Math.max(p1, p2);
    }


    public static int getSum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return sum;
    }
}
